Integrated circuits enable the rapid execution of software applications. During software development, it is necessary to analyze how well various parts of the software are functioning. This analysis may lead on to ‘de-bugging’ of the software and also software testing. De-bugging involves improving software reliability and software performance. Testing serves to exercise parts of the software.
Software is usually built up from blocks. Each block consists of a sequence of instructions that can be entered only at the beginning, and exited only at the end. So, once the program code of a block has begun running, that code will be executed until the end of the block is reached. Then the program control flow may select another block for execution.
FIG. 1 shows a control flow graph, which is a directed graph that provides a diagrammatic representation of the ‘program control flow’ of the piece of software. A control flow graph consists of vertices, each of which represents a block of software. In this description, the terms ‘software block’ and ‘vertex’ mean the same. The vertices in FIG. 1 are numbered 1-14. The control flow graph also shows ‘edges’, which are the directed arrows connecting the vertices. The software execution flows along the edges, between blocks.
When a piece of software runs, it is important to gather information about which blocks are executed. This information is gathered by ‘instrumenting’ the source code. The source code of a block is instrumented by placing a ‘probe’ into it. A probe is a set of instructions whose task is to detect and signal when a particular block runs.
When a probe is encountered during execution of a block, the probe performs an action or set of actions. These actions may include: incrementing a counter to show how many times the block has been executed; marking a flag; or writing a token to a file. Probes may also, or alternatively, be associated with the edges of the control flow graph.
In the prior art, the simplest method of finding out when each of the program blocks executes is to place a ‘probe’ in every software block. The probe detects each time that each block operates, and signals this to a monitoring system. In effect, the program is instrumented with probes that record passes through every part of the executed program.
The probes allow control flow data to be collected. The control flow data can be used to derive various statistics about control flow execution. These statistics serve to improve understanding of how the software is functioning, and can be used in software development. For example, statistics showing which blocks are executed most frequently can indicate where development effort should be concentrated.
FIG. 2 shows one example of a prior art arrangement 200 for recording signals from probes, and deriving statistics about the operation of blocks in a program.
Integrated circuit 210 runs software that comprises various blocks. Hardware module 220 receives signals from probes located in the software blocks running on integrated circuit 210. Hardware module 220 may provide various statistics, which are derived from the signals received from the probes. Hardware modules such as 220 are known in the prior art, for example from the firm Lauterbach. PC 230 is provided both to load software onto integrated circuit 210, and to receive the information output by block 220. Alternatively, hardware module 220 may be omitted, and integrated circuit 210 may be monitored directly by PC 230. In this case, integrated circuit 210 may contain a trace buffer, which allows recording of the trace for a short period, or the execution can be recorded directly on the PC. Although FIG. 2 describes software running on integrated circuit 210, the software may be running in other systems.
In the arrangement shown in FIG. 2, the simplest way to monitor the usage of each block of software running on integrated circuit 210 is to have one probe in each block. However, there are two problems with this arrangement:
(i) Each time a probe detects and reports that its software block is running, a delay is introduced. Processing within the software block slows or may even effectively stop, when the probe detects activity and reports it to hardware module 220.
(ii) Very large amounts of data are generated, which must be stored for analysis.
Table 1 below lists eight prior art publications.
TABLE 1List of prior art referencesAuthor and title of reference[1]D. E. Knuth and F. R. Stevenson. “Optimal measurement points for program frequencycounts”, BIT, 13(3): 313-322, 1973.[2]Thomas Ball and James R. Larus, “Optimally profiling and tracing programs” ACMTransactions on Programming Languages and Systems, 16(4): 1319-1360, July 1994.[3]Thomas Ball, James R. Larus “Optimally profiling and tracing programs”, Proceedings ofthe 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages POPL ′92[4]Thomas Ball, James R. Larus, “Efficient path profiling”, Proceedings of the 29th annualACM/IEEE international symposium on Microarchitecture MICRO 29 Dec. 1996[5]James R. Larus, “Efficient Program Tracing”, IEEE Computer, 26, 5 May 1993, pp 52-61[6]Hiralal Agrawal. “Dominators, super blocks, and program coverage”, In Conference Recordof POPL - 94: 21st ACM SIGPLAN-SIGACT Symposium on Principles of ProgrammingLanguages, pages 25-34, Portland, Oregon, 1994.[7]Youfeng Wu, ‘Software profiling method and apparatus’, U.S. Pat. no. 6,668,372[8]K. R. Vogel, ‘Method and system for selecting instrumentation points in a computerprogram’, U.S. Pat. No. 5,790,858
Three statistical measures are of particular importance in software development. These are ‘Profiling’, ‘Code coverage’, and ‘Tracing’. Each can serve in the study, analysis and reporting of the behavior of software.
(i) Profiling.
Signals from the blocks can show how often each block of code is executed. So profiling can be used to decide where a greater proportion of software development effort should be focused, e.g. effort to speed up the execution of blocks.
(ii) Code Coverage.
Code coverage identifies which blocks of code were executed at least once, and which were not. It may also be of interest to find out which edges were executed. For example, ‘Modified Condition/decision coverage’ (MC/DC coverage) involves both blocks and edges. Code coverage is important for verifying software.
(iii) Tracing.
Tracing involves recording which blocks were executed when a program ran, and in which sequence. A trace also provides a count of how many times the same blocks are included in the trace, which is information needed for profiling. Furthermore, tracing provides information about whether or not any particular block is in the trace at all, which is information needed for code coverage.
In order to implement each of techniques (i)-(iii) above, probes are inserted into appropriate blocks. The probes may provide information to:    (i) Counters, in order to infer execution frequencies for profiling;    (ii) Action markers for the executed blocks, for code coverage; and/or    (iii) Tokens to reconstruct the execution trace, for tracing.
A known arrangement for deriving a minimal profiling solution involves constructing a ‘spanning tree’. This method can provide the ‘Knuth solution’ to the profiling problem, referred to in prior art reference [1]. The method involves the following steps:
Step 1.
Create a control flow graph, such as that in FIG. 1, with a vertex for each block of code in a piece of software, and edges connecting the vertices.
Step 2.
Based on the control flow graph, construct a ‘reduced graph’. On the reduced graph, each edge corresponds to a vertex on the control flow graph. As the control flow graph edges are merged to represent flow through each vertex, the vertices have to be merged as well. The merged vertices in the reduced graph are called ‘super vertices’.
Step 3.
Find a spanning tree of the reduced graph. A weight may be assigned to each reduced graph edge, in order to find a minimal spanning tree. The weight is usually an estimated execution frequency. The spanning tree contains all super vertices and some reduced graph edges, so all the super vertices are connected. Usually, the spanning tree is found by starting from the super vertices and iteratively adding the reduced graph edges, until all super vertices are connected but there is no loop.
Step 4.
The set of edges on the reduced graph spanning tree is now the smallest set of edges that connects all super vertices. These edges correspond to original control flow graph vertices that represent the minimal profiling solution.
In the above approach, the spanning tree is constructed by a process of adding edges to the reduced graph, until the spanning tree is complete.
Returning to the prior art documents listed in Table 1 above:    (i) A known approach to the profiling problem was developed by Knuth, see reference [1]. Knuth applied Kirchhoff's laws to determine a minimal set of vertices. From that minimal set of vertices and their collected execution frequencies, it is possible to infer execution frequencies of all vertices. Counter probes are then only placed in blocks belonging to the minimal set of vertices. This profiling solution reduces the number of blocks that have probes, thereby reducing the delay introduced.    (ii) Reference [7] focuses on software-hardware cooperation for recording a trace.    (iii) Reference [5] incorrectly states that reference [3] presents the minimal solution to the tracing problem.    (iv) References [2] and [3] show that the minimal solution for the profiling problem is also a solution for the tracing problem. However, since this profiling solution is not inherently minimal for tracing, it can't be minimal for profiling. This is because a profile can easily be inferred from a trace. Thus, the minimal profiling solution in publications [1], [2], and [3] is minimal with respect to counter assignment for profiling, but not with respect to probe allocation.
Reference [2] in Table 1 summarizes the known results, including reference [1]. Reference [2] concludes that the tracing problem is ‘Non-deterministically polynomial’ (NP) complete, and states that the profiling solution of reference [1] can be used for tracing.